package interview.huawei.tjt.training.huisu;

import java.util.*;

/**
 * 给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
 *
 * 说明：解集不能包含重复的子集。
 *
 * 示例:
 *
 * 输入: [1,2,2]
 * 输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]
 */
public class Subsets2 {

    private static List<List<Integer>> result = new ArrayList<>();
    private static List<Integer> path = new ArrayList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            String[] str = sc.nextLine().split(",");
            int[] nums = new int[str.length];
            for (int i = 0; i < str.length; i ++) {
                if (!str[i].equals("") && str[i] != null) {
                    nums[i] = Integer.parseInt(String.valueOf(str[i]));
                }
            }
            Arrays.sort(nums);
            if (nums.length == 0){
                result.add(new ArrayList<>());
                System.out.println(result);
            } else {
                helper(nums, 0);
                System.out.println(result);
            }
            // 清理上一次的输出结果
            result.clear();
        }

    }

    private static void helper (int[] nums, int startIndex) {
        // 排除重复子集
        Collections.sort(path);
        if (result.contains(path)) {
            return;
        }
        // 这里在第一次调用时可以添加一个空集的子集，因此在main函数里面不需要再添加子集
        result.add(new ArrayList<>(path));
        if (startIndex > nums.length) {
            return;
        }

        for (int i = startIndex; i < nums.length; i ++) {
            path.add(nums[i]);
            helper(nums, i + 1);
            // 回溯
            path.remove(path.size() - 1);
        }
    }

}
